Search for: All records

Abstract Counting independent sets in graphs and hypergraphs under a variety of restrictions is a classical question with a long history. It is the subject of the celebrated container method which found numerous spectacular applications over the years. We consider the question of how many independent sets we can have in a graph under structural restrictions. We show that any$$n$$-vertex graph with independence number$$\alpha$$without$$bK_a$$as an induced subgraph has at most$$n^{O(1)} \cdot \alpha ^{O(\alpha )}$$independent sets. This substantially improves the trivial upper bound of$$n^{\alpha },$$whenever$$\alpha \le n^{o(1)}$$and gives a characterisation of graphs forbidding which allows for such an improvement. It is also in general tight up to a constant in the exponent since there exist triangle-free graphs with$$\alpha ^{\Omega (\alpha )}$$independent sets. We also prove that if one in addition assumes the ground graph is chi-bounded one can improve the bound to$$n^{O(1)} \cdot 2^{O(\alpha )}$$which is tight up to a constant factor in the exponent. 

Abstract An edge‐coloured graph is said to berainbowif no colour appears more than once. Extremal problems involving rainbow objects have been a focus of much research over the last decade as they capture the essence of a number of interesting problems in a variety of areas. A particularly intensively studied question due to Keevash, Mubayi, Sudakov and Verstraëte from 2007 asks for the maximum possible average degree of a properly edge‐coloured graph on vertices without a rainbow cycle. Improving upon a series of earlier bounds, Tomon proved an upper bound of for this question. Very recently, Janzer–Sudakov and Kim–Lee–Liu–Tran independently removed the term in Tomon's bound, showing a bound of . We prove an upper bound of for this maximum possible average degree when there is no rainbow cycle. Our result is tight up to the term, and so, it essentially resolves this question. In addition, we observe a connection between this problem and several questions in additive number theory, allowing us to extend existing results on these questions for abelian groups to the case of non‐abelian groups. 

Abstract In 1977, Erd̋s and Hajnal made the conjecture that, for every graph $$H$$, there exists $c>0$ such that every $$H$$-free graph $$G$$ has a clique or stable set of size at least $$|G|^{c}$$, and they proved that this is true with $$ |G|^{c}$$ replaced by $$2^{c\sqrt{\log |G|}}$$. Until now, there has been no improvement on this result (for general $$H$$). We prove a strengthening: that for every graph $$H$$, there exists $c>0$ such that every $$H$$-free graph $$G$$ with $$|G|\ge 2$$ has a clique or stable set of size at least $$ \begin{align*} &2^{c\sqrt{\log |G|\log\log|G|}}.\end{align*} $$ Indeed, we prove the corresponding strengthening of a theorem of Fox and Sudakov, which in turn was a common strengthening of theorems of Rödl, Nikiforov, and the theorem of Erd̋s and Hajnal mentioned above. 

A classical problem, due to Gerencsér and Gyárfás from 1967, asks how large a monochromatic connected component can we guarantee in any r-edge colouring of Kn? We consider how big a connected component can we guarantee in any r-edge colouring of Kn if we allow ourselves to use up to s colours. This is actually an instance of a more general question of Bollobás from about 20 years ago which asks for a k-connected subgraph in the same setting. We complete the picture in terms of the approximate behaviour of the answer by determining it up to a logarithmic term, provided n is large enough. We obtain more precise results for certain regimes which solve a problem of Liu, Morris and Prince from 2007, as well as disprove a conjecture they pose in a strong form. We also consider a generalisation in a similar direction of a question first considered by Erdős and Rényi in 1956, who considered given n and m, what is the smallest number of m-cliques which can cover all edges of Kn? This problem is essentially equivalent to the question of what is the minimum number of vertices that are certain to be incident to at least one edge of some colour in any r-edge colouring of Kn. We consider what happens if we allow ourselves to use up to s colours. We obtain a more complete understanding of the answer to this question for large n, in particular determining it up to a constant factor for all 1≤s≤r, as well as obtaining much more precise results for various ranges including the correct asymptotics for essentially the whole range. 

We study the following question raised by Erdős and Hajnal in the early 90’s. Over all n n -vertex graphs G G what is the smallest possible value of m m for which any m m vertices of G G contain both a clique and an independent set of size log ⁡ n \log n ? We construct examples showing that m m is at most 2 2 ( log ⁡ log ⁡ n ) 1 / 2 + o ( 1 ) 2^{2^{(\log \log n)^{1/2+o(1)}}} obtaining a twofold sub-polynomial improvement over the upper bound of about n \sqrt {n} coming from the natural guess, the random graph. Our (probabilistic) construction gives rise to new examples of Ramsey graphs, which while having no very large homogenous subsets contain both cliques and independent sets of size log ⁡ n \log n in any small subset of vertices. This is very far from being true in random graphs. Our proofs are based on an interplay between taking lexicographic products and using randomness. 

Abstract The classical Hadwiger conjecture dating back to 1940s states that any graph of chromatic number at leastrhas the clique of orderras a minor. Hadwiger's conjecture is an example of a well‐studied class of problems asking how large a clique minor one can guarantee in a graph with certain restrictions. One problem of this type asks what is the largest size of a clique minor in a graph onnvertices of independence numberat mostr. If true Hadwiger's conjecture would imply the existence of a clique minor of order. Results of Kühn and Osthus and Krivelevich and Sudakov imply that if one assumes in addition thatGisH‐free for some bipartite graphHthen one can find a polynomially larger clique minor. This has recently been extended to triangle‐free graphs by Dvořák and Yepremyan, answering a question of Norin. We complete the picture and show that the same is true for arbitrary graphH, answering a question of Dvořák and Yepremyan. In particular, we show that any‐free graph has a clique minor of order, for some constantdepending only ons. The exponent in this result is tight up to a constant factor in front of theterm.